package com.fjh.algorithm.structure.linked;

/**
 * @desc: 206 链表反转
 * @author: 范佳慧
 * @date 2021/3/17 15:39
 */
public class ReverseList {

    /**
     * 方法一：双指针迭代
     *
     *
     * 执行耗时:0 ms,击败了100.00% 的Java用户
     * 内存消耗:38.3 MB,击败了50.61% 的Java用户
     */
    public static ListNode reverseList1(ListNode head) {
        // 新建前指针 指向 空
        ListNode pre = null;
        // 新建当前指针 指向 head
        ListNode cur = head;
        while (cur != null) {
            ListNode tmp = cur.next; // 临时指针 记录 下一个元素
            cur.next = pre; // 当前元素的下一个元素 指向 前面元素
            pre = cur; // 前面指针 向前移动 指向 当前元素
            cur = tmp; // 当前指针 向前移动 指向 下一个元素
        }
        return pre;
    }

    /**
     * 方法二：递归
     * @param head
     * @return
     */
    public static ListNode reverseList2(ListNode head){
        // 终止递归
        if (head == null || head.next == null) {
            return head;
        }
        // 开始递归
        ListNode cur = reverseList2(head.next);
        /**
         * 如果链表是 1->2->3->4->5，那么此时的cur就是5
         * 而head是4，head的下一个是5，下下一个是空
         * 所以head.next.next 就是5->4
         */
        head.next.next = head;
        // 防止链表循环，需要将head.next设置为空
        head.next = null;
        // 每层递归函数都返回cur，也就是最后一个节点
        return cur;
    }

    public static void main(String[] args) {
        ListNode node5 = new ListNode(5);
        ListNode node4 = new ListNode(4, node5);
        ListNode node3 = new ListNode(3, node4);
        ListNode node2 = new ListNode(2, node3);
        ListNode head = new ListNode(1, node2);
//        ListNode node = reverseList2(head);
        ListNode node = reverseList1(head);
    }

}
